;; e1.16

#|
implement an iterative successive squaring algorithm (b to the power of 2 n times) with theta(b, n) = log(n) space and time growth
 - we can abuse the observation that b^(n/2)^2 = b^2^(n/2) for n % 2 == 0
 - the exact state transformation is to be modelled as ab^n, such that throughout iteration this state transformation remains unchanged (b ... base, n ... exponent, a ... additional state variable, always begins at 1)

to accomplish this, we first consider the cases of even and uneven n:
 - f(b, n) = f(b^2, n/2)    ... if even
if uneven, we could simply iterate once (square b once) and proceed as if our starting point were even, we consider:
 - f(b, n) = f(b^2, n/2) * b ... if uneven
as we use ourselves an additional state variable a, a possible way to proceed is to shove b multiplications that emerge from uneven cases onto our additional state variable, such that:
 - f(a, b, n) = f(a,     b^2, n/2)   ... if even
 - f(a, b, n) = f(a * b, b,   n - 1) ... if uneven
as such, the process is bound to fall into our efficient logarithmic computation scheme

a last point of the ingenuity in this design, n == 1 base case handling is included for free
|#

; SUCCessive square
(define (succ-square-it a b n)
    (define (is-even x)
        (= (remainder x 2) 0))
    (cond ((= n 0)     a)
          ((is-even n) (succ-square-it a       (* b b) (/ n 2)))
          (else        (succ-square-it (* a b) b       (- n 1)))))
(define (succ-square b n) (succ-square-it 1 b n))

; as usual, we try to prove tail recursion
(succ-square      2 5)
(succ-square-it 1 2 5)
(succ-square-it 2 2 4)
(succ-square-it 2 4 2)
(succ-square-it 2 16 1)
(succ-square-it 32 16 0)
